413D - 2048 - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<pll> vpll;
const ll mod = 1e9 + 7;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define iset indexed_set
#define inf (1LL<<62)
#define sz(x) (int)((x).size())
#define each(a) for(auto& e: a)
#define all(v) v.begin(), v.end()
#define BIT(mask, i) (((mask) >> (i)) & 1ll)
#define ONBIT(mask, i) (mask | (1ll << i))
#define OFFBIT(mask, i) (mask &~ (1ll << i))
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define done(x){ cout << x << endl;return;}
#define f(i, n) for (int i = 0; i < n; i++)
#define f1(i, n) for (int i = 1; i < n; i++)
#define rep(i, st, end) for(ll i = st; i < end; i++)
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }
const ll N = 2e3+ 1;
ll n,K;
ll dp[N][2048+5][2];
ll arr[N];
ll shift_mask(ll mask,ll val){
    if(val>mask){
        return val;
    }
    int last=0;
    f1(k,12){
        if(ONBIT(0,k)>=val){
            last=k;
            break;
        }
        if(mask&ONBIT(0,k)){
            return val;
        }
        last=k;
    }
    if(mask!=(mask|val)){
        return (mask|val);
    }
    return shift_mask(OFFBIT(mask,last),ONBIT(0,last+1));
}
ll memo(int i,int mask,int f){
    if(i==n){
        return f;
    }
    ll &ans=dp[i][mask][f];
    if(ans!=-1){
        return ans;
    }
    ans=0;
    if(arr[i]){
        if(f){
            ans+=memo(i+1,mask,f);
        }
        else{
            int nmask=shift_mask(mask,arr[i]);
            if(nmask>=ONBIT(0,K)){
                ans+=memo(i+1,0,1);
            }
            else{
                ans+=memo(i+1,nmask,f);
            }
            ans%=mod;
        }
    }
    else{
        for(int val = 2; val <= 4; val += 2) {
			int nmask = shift_mask(mask, val);
			if (nmask >= ONBIT(0, K)) ans += memo(i + 1, 0, 1);
			else ans += memo(i + 1, nmask, f);
			ans %= mod;
		}
    }
    return ans;
}
void solve(void){
	cin>>n>>K;
    f(i,n){
        cin>>arr[i];
    }
    memset(dp,-1,sizeof dp);
    done(memo(0,0,0))
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}